<!DOCTYPE html>
    <html>
    <head>
        <meta charset="UTF-8">
        <title>stone games</title>
        <style>
</style>
        
        <link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/Microsoft/vscode/extensions/markdown-language-features/media/markdown.css">
<link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/Microsoft/vscode/extensions/markdown-language-features/media/highlight.css">
<style>
            body {
                font-family: -apple-system, BlinkMacSystemFont, 'Segoe WPC', 'Segoe UI', system-ui, 'Ubuntu', 'Droid Sans', sans-serif;
                font-size: 14px;
                line-height: 1.6;
            }
        </style>
        <style>
.task-list-item { list-style-type: none; } .task-list-item-checkbox { margin-left: -20px; vertical-align: middle; }
</style>
        
        
        
    </head>
    <body class="vscode-light">
        <h1 id="stone-games">stone games</h1>
<h1 id="1-stone-game-1">1. stone game 1</h1>
<p>leetcode 877. Stone Game</p>
<ul>
<li><a href="https://www.youtube.com/watch?v=WxpIHvsu1RI&amp;list=PLrmLmBdmIlpsHaNTPP_jHHDx_os9ItYXr&amp;index=25">https://www.youtube.com/watch?v=WxpIHvsu1RI&amp;list=PLrmLmBdmIlpsHaNTPP_jHHDx_os9ItYXr&amp;index=25</a></li>
<li><a href="https://github.com/mission-peace/interview/blob/master/src/com/interview/dynamic/NPotGold.java">https://github.com/mission-peace/interview/blob/master/src/com/interview/dynamic/NPotGold.java</a></li>
<li><a href="https://leetcode.com/problems/stone-game/">https://leetcode.com/problems/stone-game/</a></li>
</ul>
<pre><code><code><div>Example 1:

Input: [5,3,4,5]
Output: true
Explanation: 
Alex starts first, and can only take the first 5 or the last 5.
Say he takes the first 5, so that the row becomes [3, 4, 5].
If Lee takes 3, then the board is [4, 5], and Alex takes 5 to win with 10 points.
If Lee takes the last 5, then the board is [3, 4], and Alex takes 4 to win with 9 points.
This demonstrated that taking the first 5 was a winning move for Alex, so we return true.
</div></code></code></pre>
<p>两位选手只能从2侧开始拿石头，一次只能拿一堆。  谁拿的最多谁赢， 本题是判断第一个拿的人能不能赢。</p>
<h2 id="11-dp-bottom-to-top">1.1 dp, bottom to top</h2>
<pre><code class="language-python"><div><span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">stoneGame</span><span class="hljs-params">(self, piles: List[int])</span> -&gt; bool:</span>
        n = len(piles)
        dp = [[(<span class="hljs-number">0</span>,<span class="hljs-number">0</span>)] * n <span class="hljs-keyword">for</span> _ <span class="hljs-keyword">in</span> range(n)]
        
        <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(n):
            dp[i][i] = (piles[i], <span class="hljs-number">0</span>)
            
        <span class="hljs-keyword">for</span> l <span class="hljs-keyword">in</span> range(<span class="hljs-number">1</span>,n):
            <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(n-l):
                j = i + l
                m1 = piles[i] + dp[i+<span class="hljs-number">1</span>][j][<span class="hljs-number">1</span>]
                m2 = piles[j] + dp[i][j<span class="hljs-number">-1</span>][<span class="hljs-number">1</span>]
                <span class="hljs-keyword">if</span> m1 &gt;= m2:
                    dp[i][j] = (m1, dp[i+<span class="hljs-number">1</span>][j][<span class="hljs-number">0</span>])
                <span class="hljs-keyword">else</span>:
                    dp[i][j] = (m2, dp[i][j<span class="hljs-number">-1</span>][<span class="hljs-number">0</span>])
                    
        <span class="hljs-keyword">return</span> dp[<span class="hljs-number">0</span>][n<span class="hljs-number">-1</span>][<span class="hljs-number">0</span>] &gt; dp[<span class="hljs-number">0</span>][n<span class="hljs-number">-1</span>][<span class="hljs-number">1</span>]
    
</div></code></pre>
<h2 id="12-dfs--memo-top-to-bottom">1.2 dfs + memo, top to bottom</h2>
<pre><code class="language-python"><div><span class="hljs-keyword">from</span> functools <span class="hljs-keyword">import</span> lru_cache

<span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">stoneGame</span><span class="hljs-params">(self, piles)</span>:</span>
        N = len(piles)

<span class="hljs-meta">        @lru_cache(None)</span>
        <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">dp</span><span class="hljs-params">(i, j)</span>:</span>
            <span class="hljs-comment"># The value of the game [piles[i], piles[i+1], ..., piles[j]].</span>
            <span class="hljs-keyword">if</span> i &gt; j: <span class="hljs-keyword">return</span> <span class="hljs-number">0</span>
            parity = (j - i - N) % <span class="hljs-number">2</span>
            <span class="hljs-keyword">if</span> parity == <span class="hljs-number">1</span>:  <span class="hljs-comment"># first player</span>
                <span class="hljs-keyword">return</span> max(piles[i] + dp(i+<span class="hljs-number">1</span>,j), piles[j] + dp(i,j<span class="hljs-number">-1</span>))
            <span class="hljs-keyword">else</span>:
                <span class="hljs-keyword">return</span> min(-piles[i] + dp(i+<span class="hljs-number">1</span>,j), -piles[j] + dp(i,j<span class="hljs-number">-1</span>))

        <span class="hljs-keyword">return</span> dp(<span class="hljs-number">0</span>, N - <span class="hljs-number">1</span>) &gt; <span class="hljs-number">0</span>
</div></code></pre>
<h2 id="13-math">1.3 math</h2>
<ul>
<li><a href="https://leetcode.com/problems/stone-game/solution/">https://leetcode.com/problems/stone-game/solution/</a></li>
</ul>
<p>本题其实先手必胜，可以证明</p>
<p>Intuition and Algorithm</p>
<p>Alex clearly always wins the 2 pile game. With some effort, we can see that she always wins the 4 pile game.</p>
<p>If Alex takes the first pile initially, she can always take the third pile. If she takes the fourth pile initially, she can always take the second pile. At least one of first + third, second + fourth is larger, so she can always win.</p>
<p>We can extend this idea to N piles. Say the first, third, fifth, seventh, etc. piles are white, and the second, fourth, sixth, eighth, etc. piles are black. Alex can always take either all white piles or all black piles, and one of the colors must have a sum number of stones larger than the other color.</p>
<p>Hence, Alex always wins the game.</p>
<pre><code class="language-python"><div><span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">stoneGame</span><span class="hljs-params">(self, piles)</span>:</span>
        <span class="hljs-keyword">return</span> <span class="hljs-literal">True</span>
</div></code></pre>
<h1 id="2-stone-game-1140-stone-game-ii">2. stone game  1140. Stone Game II</h1>
<ul>
<li><a href="https://leetcode.com/problems/stone-game-ii/">https://leetcode.com/problems/stone-game-ii/</a></li>
</ul>
<h2 id="21-top-to-bottom-dfs--memo">2.1 top to bottom, dfs + memo</h2>
<ul>
<li><a href="https://leetcode.com/problems/stone-game-ii/discuss/345230/Python-DP-Solution">https://leetcode.com/problems/stone-game-ii/discuss/345230/Python-DP-Solution</a></li>
</ul>
<p>dp[i, m] = maximum stones the current player can get from piles[i:] with M=m</p>
<p>A[i]= total stones of piles[i:]</p>
<pre><code>when current player pick stones from i to i+x-1
-&gt; the other player's stones: dp[i+x, max(m, x)]
-&gt; total stones of current player: A[i] - dp[i+x, max(m, x)]
we want the current player gets maximum means the other player gets minimum
</code></pre>
<pre><code class="language-python"><div>    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">stoneGameII</span><span class="hljs-params">(self, A: List[int])</span> -&gt; int:</span>
        N = len(A)
        <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(N - <span class="hljs-number">2</span>, <span class="hljs-number">-1</span>, <span class="hljs-number">-1</span>):
            A[i] += A[i + <span class="hljs-number">1</span>]
        <span class="hljs-keyword">from</span> functools <span class="hljs-keyword">import</span> lru_cache
<span class="hljs-meta">        @lru_cache(None)</span>
        <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">dp</span><span class="hljs-params">(i, m)</span>:</span>
            <span class="hljs-keyword">if</span> i + <span class="hljs-number">2</span> * m &gt;= N: <span class="hljs-keyword">return</span> A[i]
            <span class="hljs-keyword">return</span> A[i] - min(dp(i + x, max(m, x)) <span class="hljs-keyword">for</span> x <span class="hljs-keyword">in</span> range(<span class="hljs-number">1</span>, <span class="hljs-number">2</span> * m + <span class="hljs-number">1</span>))
        <span class="hljs-keyword">return</span> dp(<span class="hljs-number">0</span>, <span class="hljs-number">1</span>)
</div></code></pre>
<h2 id="22-bottom-to-top-dp-on3">2.2 bottom to top, dp  O(n^3)</h2>
<ul>
<li><a href="https://leetcode.com/problems/stone-game-ii/discuss/345404/Simple-DP-Solution-clean-Code">https://leetcode.com/problems/stone-game-ii/discuss/345404/Simple-DP-Solution-clean-Code</a></li>
</ul>
<pre><code><code><div>dp[i][j] is the maximum number of stones Alex can get when starting at index i with M = j
sum[i] is the total number of stones from index i to the end
The dp matrix for Lee is the same. And the stragegy for Alex is to choose an optimal X to minimize the number of stones Lee can get when starting at index (i + X) with M = max(X,j). Here we have the recurrence formula

dp[i][j] = max(sufsum[i] - dp[i + X][max(j, X)]) where 1&lt;= X &lt;= 2*j;
</div></code></code></pre>
<pre><code class="language-c++"><div><span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span> {</span>
<span class="hljs-keyword">public</span>:
    <span class="hljs-function"><span class="hljs-keyword">int</span> <span class="hljs-title">stoneGameII</span><span class="hljs-params">(<span class="hljs-built_in">vector</span>&lt;<span class="hljs-keyword">int</span>&gt;&amp; piles)</span> </span>{
        <span class="hljs-keyword">int</span> n = piles.size();
        <span class="hljs-keyword">if</span>(n == <span class="hljs-number">0</span>)  <span class="hljs-keyword">return</span> <span class="hljs-number">0</span>;
        
        <span class="hljs-built_in">vector</span>&lt;<span class="hljs-keyword">int</span>&gt;sum(n+<span class="hljs-number">1</span>, <span class="hljs-number">0</span>);
        
        <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i= n - <span class="hljs-number">1</span>; i &gt;= <span class="hljs-number">0</span>; i--)  sum[i] = piles[i] + sum[i+<span class="hljs-number">1</span>];
        
        <span class="hljs-built_in">vector</span>&lt;<span class="hljs-built_in">vector</span>&lt;<span class="hljs-keyword">int</span>&gt;&gt;dp(n+<span class="hljs-number">1</span>, <span class="hljs-built_in">vector</span>&lt;<span class="hljs-keyword">int</span>&gt;(n+<span class="hljs-number">1</span>,<span class="hljs-number">0</span>));
        <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i = <span class="hljs-number">0</span>; i &lt;= n; i++)
            dp[i][n] = sum[i];
        
        <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i = n <span class="hljs-number">-1</span>; i &gt;= <span class="hljs-number">0</span>; i--)
        {
            <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> j = n - <span class="hljs-number">1</span>; j &gt;= <span class="hljs-number">0</span>; j--)
            {
                <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> x = <span class="hljs-number">1</span>; x &lt;= <span class="hljs-number">2</span> * j &amp;&amp; i + x &lt;= n; x++)
                    dp[i][j] = max(dp[i][j], sum[i] - dp[i+x][max(j,x)]);
            }
        }
        <span class="hljs-keyword">return</span> dp[<span class="hljs-number">0</span>][<span class="hljs-number">1</span>];
    }
};
</div></code></pre>
<h1 id="3-stone-game-iii-leetcode-1406-stone-game-iii">3. stone game III leetcode 1406. Stone Game III</h1>
<ul>
<li><a href="https://leetcode.com/problems/stone-game-iii/">https://leetcode.com/problems/stone-game-iii/</a></li>
</ul>
<h2 id="31-我最开始的dfs--memo算法会超时">3.1 我最开始的dfs + memo算法，会超时</h2>
<pre><code class="language-python"><div><span class="hljs-keyword">from</span> functools <span class="hljs-keyword">import</span> lru_cache

<span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">stoneGameIII</span><span class="hljs-params">(self, stoneValue: List[int])</span> -&gt; str:</span>
        n = len(stoneValue)
        total = sum(stoneValue)
        
<span class="hljs-meta">        @lru_cache(None)</span>
        <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">_dfs</span><span class="hljs-params">(i, v1,  v2)</span>:</span>
            <span class="hljs-comment">#print(f"_dfs {i} {n} {v1} {v2}")</span>
            <span class="hljs-keyword">if</span> i == n:
                <span class="hljs-keyword">return</span> v1, v2
            
            
            r1 = _dfs(i+<span class="hljs-number">1</span>, v2, v1+stoneValue[i])
            v1a = r1[<span class="hljs-number">1</span>]
            v1b = r1[<span class="hljs-number">0</span>]
            <span class="hljs-comment">#print(f"  {i} r1={r1} {v1a} {v1b}")</span>
            
            <span class="hljs-keyword">if</span> i &lt; n<span class="hljs-number">-1</span>:
                r2 = _dfs(i+<span class="hljs-number">2</span>, v2, v1+sum(stoneValue[i:i+<span class="hljs-number">2</span>]) )
                v2a = r2[<span class="hljs-number">1</span>]
                v2b = r2[<span class="hljs-number">0</span>]
                <span class="hljs-keyword">if</span> v1a &lt; v2a:
                    v1a = v2a
                    v1b = v2b
                <span class="hljs-comment">#print(f"  {i} r2={r2} {v1a} {v1b}")</span>
            <span class="hljs-keyword">if</span> i &lt; n<span class="hljs-number">-2</span>:
                r3 = _dfs(i+<span class="hljs-number">3</span>, v2, v1+sum(stoneValue[i:i+<span class="hljs-number">3</span>]))
                v3a = r3[<span class="hljs-number">1</span>]
                v3b = r3[<span class="hljs-number">0</span>]
                <span class="hljs-keyword">if</span> v1a &lt; v3a:
                    v1a = v3a
                    v1b = v3b
                <span class="hljs-comment">#print(f"  {i} r3={r3} {v1a} {v1b}")</span>
                
            <span class="hljs-comment">#print(f"_dfs {i} {v1} {v2}, {v1a} {v1b}")</span>
            <span class="hljs-keyword">return</span> v1a, v1b
        
        
        alice, bob = _dfs(<span class="hljs-number">0</span>, <span class="hljs-number">0</span>, <span class="hljs-number">0</span>)
  
        <span class="hljs-comment">#print(f"alice={alice} bob={bob} total={total}")</span>
        <span class="hljs-keyword">if</span> bob &gt; alice:
            <span class="hljs-keyword">return</span> <span class="hljs-string">"Bob"</span>
        <span class="hljs-keyword">elif</span> bob &lt; alice:
            <span class="hljs-keyword">return</span> <span class="hljs-string">"Alice"</span>
        <span class="hljs-keyword">else</span>:
            <span class="hljs-keyword">return</span> <span class="hljs-string">"Tie"</span>
               
</div></code></pre>
<p>上面的代码可以简化为, 但还是会超时</p>
<pre><code class="language-python"><div><span class="hljs-keyword">import</span> operator

<span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">stoneGameIII</span><span class="hljs-params">(self, stoneValue: List[int])</span> -&gt; str:</span>
        n = len(stoneValue)
        total = sum(stoneValue)
        suffix = [<span class="hljs-number">0</span>] * (n+<span class="hljs-number">1</span>)
        <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(n<span class="hljs-number">-1</span>, <span class="hljs-number">-1</span>, <span class="hljs-number">-1</span>):
            suffix[i] = suffix[i+<span class="hljs-number">1</span>] + stoneValue[i]
        
<span class="hljs-meta">        @lru_cache(None)</span>
        <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">_dfs</span><span class="hljs-params">(i, v1,  v2)</span>:</span>
            <span class="hljs-keyword">if</span> i == n:
                <span class="hljs-keyword">return</span> v1, v2
            
            v1a = -float(<span class="hljs-string">'inf'</span>)
            v1b = <span class="hljs-number">0</span>
            <span class="hljs-keyword">for</span> j <span class="hljs-keyword">in</span> range(<span class="hljs-number">1</span>,<span class="hljs-number">4</span>):
                <span class="hljs-keyword">if</span> i + j &gt; n:
                    <span class="hljs-keyword">break</span>
                r = _dfs(i+j, v2, v1+suffix[i] - suffix[i+j])
                <span class="hljs-keyword">if</span> v1a &lt; r[<span class="hljs-number">1</span>]:
                    v1a = r[<span class="hljs-number">1</span>]
                    v1b = r[<span class="hljs-number">0</span>]
            <span class="hljs-keyword">return</span> v1a, v1b
        
        
        alice, bob = _dfs(<span class="hljs-number">0</span>, <span class="hljs-number">0</span>, <span class="hljs-number">0</span>)
  
        <span class="hljs-keyword">if</span> bob &gt; alice:
            <span class="hljs-keyword">return</span> <span class="hljs-string">"Bob"</span>
        <span class="hljs-keyword">elif</span> bob &lt; alice:
            <span class="hljs-keyword">return</span> <span class="hljs-string">"Alice"</span>
        <span class="hljs-keyword">else</span>:
            <span class="hljs-keyword">return</span> <span class="hljs-string">"Tie"</span>
    
    
</div></code></pre>
<p>参考了下面3.2 的算法后，重新写了这个 dfs + memo算法, 终于能通过了, 从前往后遍历</p>
<pre><code class="language-python"><div><span class="hljs-keyword">from</span> functools <span class="hljs-keyword">import</span> lru_cache

<span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">stoneGameIII</span><span class="hljs-params">(self, stoneValue: List[int])</span> -&gt; str:</span>
        n = len(stoneValue)
        suffix = [<span class="hljs-number">0</span>] * (n+<span class="hljs-number">1</span>)
        <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(n<span class="hljs-number">-1</span>, <span class="hljs-number">-1</span>, <span class="hljs-number">-1</span>):
            suffix[i] = suffix[i+<span class="hljs-number">1</span>] + stoneValue[i]
        
<span class="hljs-meta">        @lru_cache(None)</span>
        <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">_dfs</span><span class="hljs-params">(i)</span>:</span>
            <span class="hljs-keyword">if</span> i == n:
                <span class="hljs-keyword">return</span> <span class="hljs-number">0</span>
            r = -float(<span class="hljs-string">'inf'</span>)
            <span class="hljs-keyword">for</span> j <span class="hljs-keyword">in</span> range(<span class="hljs-number">1</span>,<span class="hljs-number">4</span>):
                <span class="hljs-keyword">if</span> i + j &gt; n:
                    <span class="hljs-keyword">break</span>
                r = max(r, suffix[i] - _dfs(i+j))
            <span class="hljs-keyword">return</span> r
        
        
        alice = _dfs(<span class="hljs-number">0</span>)
  
        <span class="hljs-keyword">if</span> alice*<span class="hljs-number">2</span> == suffix[<span class="hljs-number">0</span>]:
            <span class="hljs-keyword">return</span> <span class="hljs-string">"Tie"</span>
        <span class="hljs-keyword">elif</span> alice*<span class="hljs-number">2</span> &gt; suffix[<span class="hljs-number">0</span>]:
            <span class="hljs-keyword">return</span> <span class="hljs-string">"Alice"</span>
        <span class="hljs-keyword">else</span>:
            <span class="hljs-keyword">return</span> <span class="hljs-string">"Bob"</span>
    
</div></code></pre>
<h2 id="32-dp-社区的答案-bottom-to-top-dp-从后往前遍历">3.2 dp 社区的答案, bottom to top, dp, 从后往前遍历</h2>
<ul>
<li>从后往前遍历</li>
<li>和stone game II 一样，先要计算后缀和数组</li>
<li>对dp的初值设置， dp[-1]必须为0， 不然对测试用例[1,2,3,-9], 会得到错误的dp 数组 [-inf, inf, inf, -inf]</li>
</ul>
<p>dp[i] 表示面对 stoneValue[i:] 的情况下，能拿到的最大数目, 例如对测试用例 [1,2,3,7], 我们从后往前遍历.</p>
<pre><code><code><div>面对[]的时候
dp[4] = 0 这是初值

面对[7]的时候，只有一种选择
dp[3] = 7 

面对[3,7]的时候， 有两种选择
        suffix[2] - dp[3]  = 10 - 7 = 3    # 拿第1堆
        suffix[2] - dp[4]  = 10 - 0 = 10    # 拿第1，2堆
dp[2] = 10

面对[2,3,7]的时候，有3种选择
        suffix[1] - dp[2]  = 12 - 10 = 2    # 拿第1堆
        suffix[1] - dp[3]  = 12 - 7 = 5     # 拿第1, 2堆
        suffix[1] - dp[4]  = 12 - 0 = 12    # 拿第1，2, 3堆
dp[1] = 12

面对[1,2,3,7]的时候，有3种选择
        suffix[0] - dp[1]  = 13 - 12 = 1    # 拿第1堆
        suffix[0] - dp[2]  = 13 - 10 = 3     # 拿第1, 2堆
        suffix[0] - dp[3]  = 13 - 7 = 6    # 拿第1，2, 3堆
dp[0] = 6

</div></code></code></pre>
<p>具体代码</p>
<pre><code class="language-python"><div><span class="hljs-keyword">import</span> operator

<span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">stoneGameIII</span><span class="hljs-params">(self, stoneValue: List[int])</span> -&gt; str:</span>
        n = len(stoneValue)
        suffix = [<span class="hljs-number">0</span>] * (n+<span class="hljs-number">1</span>)
        <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(n<span class="hljs-number">-1</span>, <span class="hljs-number">-1</span>, <span class="hljs-number">-1</span>):
            suffix[i] = suffix[i+<span class="hljs-number">1</span>] + stoneValue[i]
            
        dp = [-float(<span class="hljs-string">'inf'</span>)] * n + [<span class="hljs-number">0</span>]   <span class="hljs-comment"># 不能是 [-float('inf)] * (n+1)</span>
        <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(n<span class="hljs-number">-1</span>, <span class="hljs-number">-1</span>, <span class="hljs-number">-1</span>):     <span class="hljs-comment"># 从后往前遍历</span>
            <span class="hljs-keyword">for</span> j <span class="hljs-keyword">in</span> range(i, min(i+<span class="hljs-number">3</span>, n)):  <span class="hljs-comment"># 只拿前1堆i,  前2堆 i,i+1  和前3堆 i, i+1, i+2 的三种情况下。</span>
                dp[i] = max(dp[i], suffix[i] - dp[j+<span class="hljs-number">1</span>])
                
        <span class="hljs-comment">#print(dp)</span>
        <span class="hljs-keyword">if</span> dp[<span class="hljs-number">0</span>]*<span class="hljs-number">2</span> == suffix[<span class="hljs-number">0</span>]:
            <span class="hljs-keyword">return</span> <span class="hljs-string">"Tie"</span>
        <span class="hljs-keyword">elif</span> dp[<span class="hljs-number">0</span>]*<span class="hljs-number">2</span> &gt; suffix[<span class="hljs-number">0</span>]:
            <span class="hljs-keyword">return</span> <span class="hljs-string">"Alice"</span>
        <span class="hljs-keyword">else</span>:
            <span class="hljs-keyword">return</span> <span class="hljs-string">"Bob"</span>
</div></code></pre>
<p>本题还可以把空间压缩到O(1), 注意下面的cmp函数是python2 only的</p>
<pre><code class="language-python"><div>    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">stoneGameIII</span><span class="hljs-params">(self, A)</span>:</span>
        dp = [<span class="hljs-number">0</span>] * <span class="hljs-number">3</span>
        <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> xrange(len(A) - <span class="hljs-number">1</span>, <span class="hljs-number">-1</span>, <span class="hljs-number">-1</span>):
            dp[i % <span class="hljs-number">3</span>] = max(sum(A[i:i + k]) - dp[(i + k) % <span class="hljs-number">3</span>] <span class="hljs-keyword">for</span> k <span class="hljs-keyword">in</span> (<span class="hljs-number">1</span>, <span class="hljs-number">2</span>, <span class="hljs-number">3</span>))
        <span class="hljs-keyword">return</span> [<span class="hljs-string">"Tie"</span>, <span class="hljs-string">"Alice"</span>, <span class="hljs-string">"Bob"</span>][cmp(dp[<span class="hljs-number">0</span>], <span class="hljs-number">0</span>)]
</div></code></pre>
<p>为什么stone game II 要从前往后遍历， 但是stone game III 要从后往前遍历?</p>
<pre><code>我最开始以为 &quot;因为stone game II 的M 值，和之前的选择有关系，从后往前遍历的话，不能知道M值是多少。&quot;

但其实， stone II和stone III 都是支持从前往后，从后往前遍历的。 dfs+memo算法就是从前往后遍历。 而dp算法就是从后往前遍历。
</code></pre>

    </body>
    </html>